package com.study.lintcode.my.code_10;

/**********************************************************************
 * &lt;p&gt;文件名：Example_1.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(https://www.lintcode.com/problem/a-b-problem/)
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/5 21:56
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014
 *                    All Rights Reserved.
 */
public class Example_5 {
    /**
     * @param n:    An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
//        System.out.println("init:" + Arrays.toString(nums));
        if (n > nums.length) {
            return 0;
        }
        return quick_sort(nums, 0, nums.length - 1, n);
    }

    int quick_sort(int nums[], int l, int r, int n) {
        if (l < r) {
            //先成挖坑填数法调整s[]
            int middle = adjustArray(nums, l, r);
            // 递归调用  (第n大的数==第s.length - n小的数)
            if (nums.length - n < middle) {
                return quick_sort(nums, l, middle - 1, n);
            }
            if (nums.length - n > middle) {
                return quick_sort(nums, middle + 1, r, n);
            }
            return nums[middle];
        }
        return nums[nums.length - n];
    }

    //返回调整后基准数的位置
    int adjustArray(int nums[], int l, int r) {
        int i = l, j = r;
        int x = nums[l]; //nums[l]即s[i]就是第一个坑
        while (i < j) {
            // 从右向左找小于x的数来填s[i]
            while (i < j && nums[j] >= x)
                j--;
            if (i < j) {
                nums[i] = nums[j]; //将s[j]填到s[i]中，nums[j]就形成了一个新的坑
                i++;
            }

            // 从左向右找大于或等于x的数来填s[j]
            while (i < j && nums[i] < x)
                i++;
            if (i < j) {
                nums[j] = nums[i]; //将s[i]填到s[j]中，nums[i]就形成了一个新的坑
                j--;
            }
        }
        //退出时，i等于j。将x填到这个坑中。
        nums[i] = x;
//        System.out.println("sort:" + Arrays.toString(nums));
        return i;
    }

    public static void main(String[] args) {
        //0,0=>1
        //0,9=>1
        //1,12=>5
        //2,12=2
        System.out.println(new Example_5().kthLargestElement(3, new int[]{7, 8, 1, 2, 5, 4, 3}));
    }
}
